User blog:Nayuta Ito/Brainfuck challenge
Brainfuck specification: There are only 8 characters acceptable in Brainfuck. Anything else is ignored. Start with both-side infinitely long array and a pointer. (Imagine a tape and turing machine, but each cell can hold as big numbers as you want) + means to increase the value of cell the pointer is pointing. - means to decrease the value of cell the pointer is pointing. > means to move the pointer to the right. < means to move the pointer to the left. [ means where to go back from ]. ] means to go back to corresponding [ unless the pointer is pointing a zero. (I mean, not a0, but an 0) . means to display the number at which the pointer is pointing, and then halt. , means to get a number from standard input. Same as scanf in C language. (note: I slightly changed the definitions of ".") I define BF(x) as the biggest displayed number possible with x characters of Brainfuck program. Of course this is uncomputable. Some other variants: BF+(x) does not allow array to store negative number. BF+(x) does not allow to go left from the starting position. BF++(x) does not allow neither negative number or starting position. First programs are simple: BF(1)=0 . BF(2)=1 +. BF(3)=2 ++. BF(4)=3 +++. BF(5)=4 ++++. I think it will go multiplication at around 30 and exponentiation at around 60. Maybe BF(100)>G, but I'm not sure. According to Deelit11, BF(15) >= 16 ++++>++++<->. BF(16) >= 20 +++++>++++<->. BF(17) >= 25 +++++>+++++<->. BF(18) >= 30 ++++++>+++++<->. BF(19) >= 36 ++++++>++++++<->. BF(20) >= 42 +++++++>++++++<->. BF(21) >= 49 +++++++>+++++++<->. As you might see, this is multiplication. BF(29) >= 64 >+>+++[<<++>-<>++<->>-]<. //but you can do 11*11 in 29 characters with the method above BF(30) >= 256 >+>++++[<<++>-<>++<->>-]<. //this time you can do only 11*12 and this program wins BF(31) >= 1296 >+>++++[<<+++>-<>++<->>-]<. BF(32) >= 7776 >+>+++++[<<+++>-<>++<->>-]<. BF(33) >= 59,049 >+>+++++[<<+++>-<>+++<->>-]<. BF(34) >= 531,441 >+>++++++[<<+++>-<>+++<->>-]<. BF(35) >= 4,782,969 >+>+++++++[<<+++>-<>+++<->>-]<. BF(36) >= 43,046,721 >+>++++++++[<<+++>-<>+++<->>-]<. This is a bit complicated. I will explain: First, consider >+>+・・・+[<<+・・・+>-<>+・・・+<->>-]<. /w there are a,b,c pluses each. Before the first bracket, the memory is like this: 0,1,^a. (caret means the pointer) Next, in the left bracket, the memory becomes b,^0,a. Next, every time the programs ends the right brackets, memory changes like this: ^b-1,c,a ; ^b-2,2c,a ; ... ; ^0,bc,a Then go to the program goes to >>-, becoming 0,bc,^a-1. Next, that bring the program back to the outer bracket, and becomes 0,^bc,a-1. Then after the left bracket, it becomes b^2*c,^0,a-1. Then after the right bracket, it becomes ^0,b^2*c^2,a-1. Then >>-, so 0,b^2*c^2,^a-2. This ends with 0,^(bc)^a,0. Therefore, this program indicates exponentiation. B(40) >= 65534 +++[>+[>+>++<-><+>-<<-]><+>-<<-]>. //you can do (2*2)^22 B(41) >= 2^^5 - 2 ++++[>+[>+>++<-><+>-<<-]><+>-<<-]>. B(42) >= 2^^6 - 2 +++++[>+[>+>++<-><+>-<<-]><+>-<<-]>. B(43) >= 2^^7 - 2 ++++++[>+[>+>++<-><+>-<<-]><+>-<<-]>. B(44) >= 2^^8 - 2 +++++++[>+[>+>++<-><+>-<<-]><+>-<<-]>. B(45) >= 2^^9 - 2 ++++++++[>+[>+>++<-><+>-<<-]><+>-<<-]>. B(46) >= 2^^10 - 2 +++++++++[>+[>+>++<-><+>-<<-]><+>-<<-]>. B(47) >= 2^^11 - 2 ++++++++++[>+[>+>++<-><+>-<<-]><+><<-]>. B(54) >= 2^^^4 - 2 +++[>+[>+[>+>++<-><+>-<<-]><+>-<<-]><+>-<<-]>. B(55) >= 2^^^5 - 2 ++++[>+[>+[>+>++<-><+>-<<-]><+>-<<-]><+>-<<-]>. B(56) >= 2^^^6 - 2 +++++[>+[>+[>+>++<-><+>-<<-]><+>-<<-]><+>-<<-]>. B(57) >= 2^^^7 - 2 ++++++[>+[>+[>+>++<-><+>-<<-]><+>-<<-]><+>-<<-]>. B(58) >= 2^^^8 - 2 +++++++[>+[>+[>+>++<-><+>-<<-]><+>-<<-]><+>-<<-]>. BF(62) >= 65,536 +<++++[-[>[->+<<->>>+<<<>>>-<<+<+>>><-]<<-]>-<++><<]>. BF(63) >= 2^^^6 +<+++++[-[>[->+<<->>>+<<<>>>-<<+<+>>><-]<<-]>-<++><<]>. BF(64) >= 2^^^2^^^2^^^2^^^6 > 2^^^^7 +<++++++[-[>[->+<<->>>+<<<>>>-<<+<+>>><-]<<-]>-<++><<]>. BF(65) >= 2^^^^^8 +<+++++++[-[>[->+<<->>>+<<<>>>-<<+<+>>><-]<<-]>-<++><<]>. BF(66) >= 2^^^^^^9 +<++++++++[-[>[->+<<->>>+<<<>>>-<<+<+>>><-]<<-]>-<++><<]>. BF(67) >= 2^^^^^^^10 +<+++++++++[-[>[->+<<->>>+<<<>>>-<<+<+>>><-]<<-]>-<++><<]>. BF(70) >= 2^^^6 +++[->>>+<+[-[>[->+<<->>>+<<<>>>-<<+<+>>><-]<<-]>-<++><<]<]>>. BF(71) > Ack(2^^^6) ++++[->>>+<+[-[>[->+<<->>>+<<<>>>-<<+<+>>><-]<<-]>-<++><<]<]>>. BF(72) > Ack^2(2^^^6) +++++[->>>+<+[-[>[->+<<->>>+<<<>>>-<<+<+>>><-]<<-]>-<++><<]<]>>. BF(73) > Ack^3(2^^^6) ++++++[->>>+<+[-[>[->+<<->>>+<<<>>>-<<+<+>>><-]<<-]>-<++><<]<]>>. BF(88) >= 2^^^6 ++[->>>+-<<+>><<[->>>+<+[-[>[->+<<->>>+<<<>>>-<<+<+>>><-]<<-]>-<++><<]<]<]>>>. BF(89) > F_{w+1}(2^^^6 - 2) > G +++[->>>+-<<+>><<[->>>+<+[-[>[->+<<->>>+<<<>>>-<<+<+>>><-]<<-]>-<++><<]<]<]>>>. BF(90) > F_{w+1}^2(2^^^6 - 2) > F_{w+2}(2) ++++[->>>+-<<+>><<[->>>+<+[-[>[->+<<->>>+<<<>>>-<<+<+>>><-]<<-]>-<++><<]<]<]>>>. BF(91) > f_{w+2}(3) +++++[->>>+-<<+>><<[->>>+<+[-[>[->+<<->>>+<<<>>>-<<+<+>>><-]<<-]>-<++><<]<]<]>>>. Category:Blog posts